package algorithm.weightgraph;

public class MinIndexHeap<Item extends Comparable> {

    //数据
    private Item[] data;
    //在堆中对应的索引
    private int[] indexs;
    //数据对应的堆中的索引
    private int[] revise;
    //堆容量
    private int capacity;
    //现共有多少元素
    private int count;


    public MinIndexHeap(int capacity) {
        this.capacity = capacity;
        this.data = (Item[]) new Comparable[this.capacity + 1];
        this.indexs = new int[this.capacity + 1];
        this.revise = new int[this.capacity + 1];
        for (int i = 0; i < this.capacity; i++) {
            revise[i] = 0;
        }
        this.count = 0;
    }


    public void insert(int index, Item item) {
        index++;
        data[index] = item;
        indexs[++count] = index;
        revise[index] = count;
        shiftUp(count);
    }

    public void change(int index,Item item){
        index++;
        data[index] = item;
        shiftUp(revise[index]);
        shiftDown(revise[index]);

    }

    public Item exportMin() {
        Item min = data[0];
        data[0] = data[count--];
        shiftDown(0);
        return min;
    }


    private void shiftDown(Integer index) {
        int j = index * 2;
        while (j <= count) {
            if (j + 1 <= count && data[indexs[j + 1]].compareTo(data[indexs[j]]) < 0) {
                j = j + 1;
            }
            if (data[indexs[j]].compareTo(data[indexs[index]]) < 0) {
                swap(indexs, j, index);
                revise[indexs[j]] = index;
                revise[indexs[index]] = j;
                index = j;
            } else {
                break;
            }
        }
    }

    private void shiftUp(Integer index) {
        while (index > 0 && data[indexs[index / 2]].compareTo(data[indexs[index]]) > 0) {
            swap(indexs, index / 2, index);
            revise[indexs[index / 2]] = index / 2;
            revise[indexs[index]] = index;
            index = index / 2;
        }
    }


    public int getCount() {
        return count;
    }

    private void swap(Item[] arr, int i, int j) {
        Item tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }


    private void swap(int[] arr, int i, int j) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    public boolean isEmpty() {
        return count==0;
    }
}
